AustralieFrV1, Main, Exploration, bibRecord, 006468

Computing All Subtree Repeats in Ordered Ranked Trees

Identifieur interne : 006468 ( Main/Exploration ); précédent : 006467; suivant : 006469

Computing All Subtree Repeats in Ordered Ranked Trees

Auteurs : Michalis Christou [Royaume-Uni] ; Maxime Crochemore [Royaume-Uni, France] ; Tomáš Flouri [République tchèque] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Jan Janoušek [République tchèque] ; Bo Ivoj Melichar [République tchèque] ; Solon P. Pissis [Royaume-Uni]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.

RBID : ISTEX:AEC880996598D9FFB7D00EE9613630C340EF0F8F

English descriptors

KwdEn :
- Algorithm, Arity, Arity checksum, Automaton, Common subexpression problem, Complete subtree, Computer science, Function partition, Important aspects, Level array, Linear runtime, Linear time, Nding, Next factor, Node, Notation, Parent node, Preprocessing, Preprocessing phase, Pushdown, Pushdown automata, Subtree, Subtrees, Tree pattern, Triplet.
Teeft :
- Algorithm, Arity, Arity checksum, Automaton, Common subexpression problem, Complete subtree, Computer science, Function partition, Important aspects, Level array, Linear runtime, Linear time, Nding, Next factor, Node, Notation, Parent node, Preprocessing, Preprocessing phase, Pushdown, Pushdown automata, Subtree, Subtrees, Tree pattern, Triplet.

Abstract

Abstract: We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are computed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.

Url:

https://api.istex.fr/document/AEC880996598D9FFB7D00EE9613630C340EF0F8F/fulltext/pdf

DOI: 10.1007/978-3-642-24583-1_33

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 002124
to stream Istex, to step Curation: 002124
to stream Istex, to step Checkpoint: 000888
to stream Main, to step Merge: 006845
to stream Main, to step Curation: 006468

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computing All Subtree Repeats in Ordered Ranked Trees</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</author>
<author><name sortKey="Flouri, Tomas" sort="Flouri, Tomas" uniqKey="Flouri T" first="Tomáš" last="Flouri">Tomáš Flouri</name>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</author>
<author><name sortKey="Janousek, Jan" sort="Janousek, Jan" uniqKey="Janousek J" first="Jan" last="Janoušek">Jan Janoušek</name>
</author>
<author><name sortKey="Melichar, Bo Ivoj" sort="Melichar, Bo Ivoj" uniqKey="Melichar B" first="Bo Ivoj" last="Melichar">Bo Ivoj Melichar</name>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:AEC880996598D9FFB7D00EE9613630C340EF0F8F</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-24583-1_33</idno>
<idno type="url">https://api.istex.fr/document/AEC880996598D9FFB7D00EE9613630C340EF0F8F/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002124</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002124</idno>
<idno type="wicri:Area/Istex/Curation">002124</idno>
<idno type="wicri:Area/Istex/Checkpoint">000888</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000888</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Christou M:computing:all:subtree</idno>
<idno type="wicri:Area/Main/Merge">006845</idno>
<idno type="wicri:Area/Main/Curation">006468</idno>
<idno type="wicri:Area/Main/Exploration">006468</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Computing All Subtree Repeats in Ordered Ranked Trees</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
<affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London</wicri:regionArea>
<wicri:noRegion>King’s College London</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London</wicri:regionArea>
<wicri:noRegion>King’s College London</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Paris-Est</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Flouri, Tomas" sort="Flouri, Tomas" uniqKey="Flouri T" first="Tomáš" last="Flouri">Tomáš Flouri</name>
<affiliation wicri:level="3"><country xml:lang="fr">République tchèque</country>
<wicri:regionArea>Dept. of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University, Prague</wicri:regionArea>
<placeName><settlement type="city">Prague</settlement>
<region type="région" nuts="2">Bohême centrale</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London</wicri:regionArea>
<wicri:noRegion>King’s College London</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Digital Ecosystems & Business Intelligence Institute, Curtin University, Perth</wicri:regionArea>
<wicri:noRegion>Perth</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Janousek, Jan" sort="Janousek, Jan" uniqKey="Janousek J" first="Jan" last="Janoušek">Jan Janoušek</name>
<affiliation wicri:level="3"><country xml:lang="fr">République tchèque</country>
<wicri:regionArea>Dept. of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University, Prague</wicri:regionArea>
<placeName><settlement type="city">Prague</settlement>
<region type="région" nuts="2">Bohême centrale</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Melichar, Bo Ivoj" sort="Melichar, Bo Ivoj" uniqKey="Melichar B" first="Bo Ivoj" last="Melichar">Bo Ivoj Melichar</name>
<affiliation wicri:level="3"><country xml:lang="fr">République tchèque</country>
<wicri:regionArea>Dept. of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University, Prague</wicri:regionArea>
<placeName><settlement type="city">Prague</settlement>
<region type="région" nuts="2">Bohême centrale</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London</wicri:regionArea>
<wicri:noRegion>King’s College London</wicri:noRegion>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Arity</term>
<term>Arity checksum</term>
<term>Automaton</term>
<term>Common subexpression problem</term>
<term>Complete subtree</term>
<term>Computer science</term>
<term>Function partition</term>
<term>Important aspects</term>
<term>Level array</term>
<term>Linear runtime</term>
<term>Linear time</term>
<term>Nding</term>
<term>Next factor</term>
<term>Node</term>
<term>Notation</term>
<term>Parent node</term>
<term>Preprocessing</term>
<term>Preprocessing phase</term>
<term>Pushdown</term>
<term>Pushdown automata</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Tree pattern</term>
<term>Triplet</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Arity</term>
<term>Arity checksum</term>
<term>Automaton</term>
<term>Common subexpression problem</term>
<term>Complete subtree</term>
<term>Computer science</term>
<term>Function partition</term>
<term>Important aspects</term>
<term>Level array</term>
<term>Linear runtime</term>
<term>Linear time</term>
<term>Nding</term>
<term>Next factor</term>
<term>Node</term>
<term>Notation</term>
<term>Parent node</term>
<term>Preprocessing</term>
<term>Preprocessing phase</term>
<term>Pushdown</term>
<term>Pushdown automata</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Tree pattern</term>
<term>Triplet</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are computed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Royaume-Uni</li>
<li>République tchèque</li>
</country>
<region><li>Bohême centrale</li>
</region>
<settlement><li>Prague</li>
</settlement>
</list>
<tree><country name="Royaume-Uni"><noRegion><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</noRegion>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</country>
<country name="France"><noRegion><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</noRegion>
</country>
<country name="République tchèque"><region name="Bohême centrale"><name sortKey="Flouri, Tomas" sort="Flouri, Tomas" uniqKey="Flouri T" first="Tomáš" last="Flouri">Tomáš Flouri</name>
</region>
<name sortKey="Janousek, Jan" sort="Janousek, Jan" uniqKey="Janousek J" first="Jan" last="Janoušek">Jan Janoušek</name>
<name sortKey="Melichar, Bo Ivoj" sort="Melichar, Bo Ivoj" uniqKey="Melichar B" first="Bo Ivoj" last="Melichar">Bo Ivoj Melichar</name>
</country>
<country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006468 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006468 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:AEC880996598D9FFB7D00EE9613630C340EF0F8F
   |texte=   Computing All Subtree Repeats in Ordered Ranked Trees
}}

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024

	Serveur d'exploration sur les relations entre la France et l'Australie
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur les relations entre la France et l'Australie

Computing All Subtree Repeats in Ordered Ranked Trees

Computing All Subtree Repeats in Ordered Ranked Trees

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri